package com.example.Arithmetic.Arithmetic;

import com.example.Arithmetic.Arithmetic.Port.Priority;
import com.example.Arithmetic.Arithmetic.Port.Queue;

/**
 * 日期：2023/10/10
 * 时间：10:16
 * 描述：优先级队列,堆实现
 */
public class PriorityQueueHeap<E extends Priority> implements Queue<E> {
    Priority[] array;
    int size;

    public PriorityQueueHeap(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isEmpty()) {
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (child > 0 && array[parent].priority() < value.priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = value;
        return false;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0, size - 1);
        size--;
        Priority priority = array[size];
        array[size] = null;               //help GC
        Down(0);
        return (E) priority;
    }

    private void Down(int parent) {
        int left = parent * 2 + 1;
        int right = left + 1;
        int max = parent;
        if (left<size&&array[max].priority() < array[left].priority()) {
           max=left;
        }
        if (right<size&&array[max].priority() < array[right].priority()) {
            max=right;
        }
        if (max!=parent) {
            swap(max,parent);
            Down(max);
        }
    }

    private void swap(int i, int j) {
        Priority temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
